// =====================================================================================
// 
//       Filename:  find_k.cpp
// 
//    Description:  http://www.careercup.com/question?id=15381730
//    Given a 2 D array. The rows and columns are sorted.
//
//    Find the kth largest element from the 2-d array in most efficient way. Can it be done in-place?
// 
//        Version:  1.0
//        Created:  02/06/2013 08:06:13
//       Revision:  none
//       Compiler:  g++
// 
// =====================================================================================

#include <stdio.h>

int find_k(int a[][3], int n, int k)
{
	if(n <=0) return -1;
	if(k <= 0||k >n*n) return -1;

	int indices[n];
	for (int i = 0; i < n; ++i) {
		indices[i] = n-1;
	}
	int result = 0, index = 0;	
	for(int j = 0; j < k; ++j) {
		result = 0;
		for (int i = 0; i < n; ++i) {
			if(indices[i] >=0 && a[i][indices[i]] > result) {
				result = a[i][indices[i]];
				index = i;
			}
		}
		-- indices[index];
	}
	return result;
	/* code */
}

int main(int argc, const char *argv[])
{
	int a[][3] = {{1,2,3}, {4,5,6},{7,8,9}};
	for(int k = 0; k < 11; k ++)
		printf("Find %d = %d\n", k, find_k(a, 3, k));
	return 0;
}
